home *** CD-ROM | disk | FTP | other *** search
/ Tech Arsenal 1 / Tech Arsenal (Arsenal Computer).ISO / tek-04 / ndx300.zip / NDX.CPP < prev    next >
Encoding:
C/C++ Source or Header  |  1992-11-02  |  12.8 KB  |  532 lines
  1. /*  NDX.CPP  . . .  BTree Index Handling Routines
  2.  
  3.     Copyright (C) 1987, 1988, 1989, 1992 by George H. Mealy
  4.  
  5. */    
  6.  
  7. #pragma OPTION   -w-pia
  8. #pragma OPTION   -a-
  9.  
  10. #include    <stdlib.h>
  11. #include    <stdarg.h>
  12. #include    <string.h>
  13. #include    <dir.h>
  14. #include    <io.h>
  15. #include    <fcntl.h>
  16. #include    <ctype.h>
  17. #include    <sys\stat.h>
  18. #include    "ndx.h"
  19.  
  20. #define MAJOR       3
  21. #define MINOR       0
  22.  
  23. #define HDRSIZE     512
  24. #define NCACHE      10      /* Number of node buffers */
  25. #define POP(a)              a->pop(a)
  26. #define PUSH(a, b)          b->push(a)
  27.  
  28. typedef struct{             // Cache entry
  29.     char        dirty;      // Node needs writing
  30.     FILE        *handle;    // File handle
  31.     Node        *node;      // File block content
  32. } CACHE;
  33.  
  34. CACHE   cache[NCACHE];      // The node cache
  35. char    cache_exists;       // Initiated if nonzero
  36.  
  37. #define FIELDOFFSET(type, field) ((WORD)&(((type *)0)->field))
  38. unsigned Index::hdrsize = FIELDOFFSET(Index, stacktop);
  39.  
  40.  
  41. void fatal(char *format, ...);
  42.  
  43. char notice[] = "B-tree indexing routines copyright 1987,88,89,92 by"
  44.                     "George H. Mealy.";
  45. Index   *ndx;               /* Current index block */
  46. char    searcharg[maxkey];
  47. int     searchn;
  48.  
  49. Index::Index(char *name, int md, CFN compfn)    // Create new Index
  50. {
  51.     ndx = this;
  52.     handle = fopen(name, "w+b");
  53.     strcpy(filename, name);
  54.     if (!handle) fatal("Cannot open %s\n\a", name);
  55.     initcache();
  56.     stacktop = 0;
  57.     root = eof = HDRSIZE;
  58.     freelist = 0L;
  59.     major = MAJOR;
  60.     minor = MINOR;
  61.     mode = md;
  62.     newnode();
  63.     write(0L, &root, hdrsize);
  64.     write((DWORD)hdrsize, cache[0].node->keys, HDRSIZE - hdrsize);
  65.     if (compfn) cmpfn = compfn;
  66.     chsize(fileno(handle), eof);
  67. }
  68.  
  69. Index::Index(char *name, CFN compfn)
  70. {
  71.     ndx = this;
  72.     handle = fopen(name, "a+b");
  73.     if(! handle) fatal("Index file %s unavailable\n\a", name);
  74.     initcache();
  75.     strcpy(filename, name);
  76.     read(0L, &root, hdrsize);
  77.     if (compfn) cmpfn = compfn;
  78. }
  79.  
  80. Index::~Index()
  81. {
  82.     ndx = this;
  83.     for (int i=0; i < NCACHE; i++)
  84.         if (cache[i].handle == handle) {
  85.             if (cache[i].dirty) write(cache[i].node->offset,
  86.                                       cache[i].node, nodesize);
  87.             cache[i].node->offset =  cache[i].dirty = 0;
  88.             cache[i].handle = NULL;
  89.         }
  90.     write(0L, &root, hdrsize);
  91.     fclose(handle);
  92. }
  93.  
  94. //  Cache handling routines
  95.  
  96. Index::initcache()
  97. {
  98.     int i;
  99.     
  100.     if (! cache_exists) {
  101.         cache_exists++;
  102.         for (i=0; i<NCACHE; i++) {
  103.             if (! (cache[i].node = new Node)) return 0;
  104.             memset(cache[i].node, 0, nodesize);
  105.             }
  106.     }
  107.     return 1;
  108. }
  109.  
  110. Node *Index::newnode()
  111. {
  112.     Node *slot = getnode(0L);   // New slot in the cache
  113.     DWORD n;
  114.     
  115.     cache[0].dirty++;           // Mark it dirty
  116.     if (freelist) {  /* If we can use an old node
  117.                   -- that is, if the node freelist has an entry */
  118.         read(n = freelist, slot, nodesize);
  119.         freelist = slot->offset;
  120.         slot->offset = n;
  121.     }
  122.     else {                      // extend the file
  123.         slot->offset = eof;
  124.         eof += nodesize;
  125.     }
  126.     memset(slot->keys, 0, maxendkeys);  // In any case, zero the key data
  127.     return slot;
  128. }
  129.  
  130. Node * Index::getnode(DWORD offset)
  131. {
  132.     CACHE *c = cache, temp;
  133.     
  134.     for (int i=0; i < NCACHE; i++, c++)     /* It may be in the cache */
  135.         if (c->node->offset == offset && (c->handle == handle
  136.             || !offset)) break;
  137.     if (i == NCACHE) {                  /* No luck */
  138.         /* Try to find an empty slot */
  139.         for (c=cache, i=0; i < NCACHE && c->node->offset ; c++, i++) ;
  140.         /* None ... empty the last one */
  141.         if (i == NCACHE) {  
  142.             c--; i--;
  143.             write(c->node->offset, c->node, nodesize);
  144.         }
  145.         c->dirty = 0;
  146.         if (! offset) memset(c->node, 0, nodesize);
  147.             else read(offset, c->node, nodesize);
  148.     }
  149.     temp = *c;                  /* Promote it to the top */
  150.     temp.handle = handle;
  151.     memmove(cache + 1, cache, i*sizeof(CACHE));
  152.     *cache = temp;
  153.     return temp.node;
  154. }
  155.  
  156. void Index::read(DWORD start, void *buffer, unsigned n)
  157. {
  158.     if (fseek(handle, start, SEEK_SET) ||
  159.         n != fread(buffer, 1, n, handle))
  160.         fatal("Read failure on file %s\n", filename);
  161. }
  162.  
  163. void Index::write(DWORD start, void *buffer, unsigned n)
  164. {
  165.     if (fseek(handle, start, SEEK_SET) ||
  166.         n != fwrite(buffer, 1, n, handle))
  167.         fatal("Write failure on file %s\n", filename);
  168. }
  169.  
  170. Key::Key(char *k, DWORD off)
  171. {
  172.     if (strlen(k) >= maxkey) fatal("Key \"%s\" too long");
  173.     strcpy(data, k);
  174.     offset = off;
  175.     lson = 0L;
  176. }
  177.  
  178. DWORD Index::insert(char * key, DWORD offset)
  179. {
  180.     Key k(key, offset);
  181.     long result;
  182.     
  183.     ndx = this;
  184.     do {
  185.         stacktop = 0;
  186.         result = k.insert(root);
  187.         } while (result < 0);
  188.     ckey = k;
  189.     return result? k.offset: result;
  190. }
  191.  
  192. DWORD Key::insert(DWORD root)
  193. {
  194.     Node * node;
  195.     Key *k, *ik;
  196.     void *end;
  197.     int compare = -1, n;
  198.     
  199.     if (! root) return 0;
  200.     node = ndx->getnode(root);
  201.     k = (Key *)node->keys;
  202.     end = (char *)k + node->endkeys;
  203.     while (k < end &&
  204.       (compare = strcmp(k->data, data)) <= 0)
  205.         k = k->next();
  206.     if (! compare) {      /* Found it */
  207.         ik = k;
  208.         if (ndx->mode == NODUPS)
  209.             {offset = k->offset; return 0; }
  210.         for (; k < end; k = k->next()) {
  211.                 if ((compare = strcmp((char *)k->data, data)) != 0) break;
  212.                 if (k->offset == offset) return k->offset;
  213.             }
  214.         if (ndx->mode == LIFO) k = ik;
  215.         }
  216.     if (k->lson) {           /* Recurse */
  217.         PUSH(node, k);
  218.         return insert(k->lson);
  219.         }
  220.     if (node->endkeys + length() > maxendkeys) /* Node full, so split */
  221.         return node->split()? -1: 0;
  222.     node->shiftup(k, length());
  223.     PUSH(node, k->next());
  224.     k->keycpy(this);
  225.     cache[0].dirty = 1;
  226.     return k->offset;
  227. }
  228.  
  229. Index::remove(char *key, DWORD offset)
  230. {
  231.     unsigned ttop, i;
  232.     Node *node;
  233.     Key *kp;
  234.     
  235.     ndx = this;
  236.     if (key && !findkeyrec(key, offset)) return 0;
  237.     ttop = stacktop;
  238.     node = POP(kp);
  239.     if (! kp->lson) node->shiftdn(kp, kp->length(), 0);
  240.       else {
  241.         Key *tkey;
  242.  
  243.         stacktop++;
  244.         do  {   /* Find lower rightmost key to pull up */
  245.             node = getnode(kp->lson);
  246.             kp = (Key *)(node->keys + node->endkeys);
  247.             PUSH(node, kp);
  248.         } while (kp->lson);
  249.         node = POP(kp);
  250.         kp = kp->prev(node);  /* This is the key to go up */
  251.  
  252.         /* need only the offset and key */
  253.         tkey = (Key *)malloc(i = kp->length());
  254.         memcpy(tkey, kp, i);
  255.         node->shiftdn(kp, i, 1);   /* Leaves the lson part untouched */
  256.         stacktop = ttop;
  257.         node = POP(kp);
  258.  
  259.         /* Preserve the original lson */
  260.         tkey->lson = kp->lson;
  261.  
  262.         /* Substitute tkey for key being deleted */
  263.         node->endkeys++;           /* Avoid deletion of node! */
  264.         node->shiftdn(kp, kp->length(), 0);
  265.         node->endkeys--;
  266.         node->shiftup(kp, i);
  267.         memcpy(kp, tkey, i);
  268.         free(tkey);
  269.     }
  270.     ++stacktop;
  271.     while (kp->lson) {
  272.         PUSH(node, kp);
  273.         node = getnode(kp->lson);
  274.         kp = (Key *)node->keys;
  275.         }
  276.     ckey = *kp;
  277.     return 1;
  278. }
  279.  
  280. DWORD Index::findkeyrec(char *key, DWORD offset)
  281. {
  282.     DWORD rcd;
  283.  
  284.     rcd = find(key);
  285.     while (rcd && rcd != offset) rcd = next();
  286.     return rcd;
  287. }
  288.  
  289. DWORD Index::find(char *key)
  290. {
  291.     ndx = this;
  292.     if (key) {
  293.         strcpy(searcharg, key);
  294.         searchn = strlen(key);
  295.         stacktop = 0;
  296.         return _find(key, root);  /* Inner routine */
  297.     }
  298.     if (! next() ||
  299.         (ndx->cmpfn)(searcharg, ckey.data, searchn)) return NULL;
  300.     return ckey.offset;
  301. }
  302.  
  303. DWORD Index::_find(char * key, DWORD root)
  304. {
  305.     Node *node = getnode(root);
  306.     Key * k = (Key *)node->keys;
  307.     DWORD rcd;
  308.     int  compare, n = strlen(key);
  309.     
  310.     for (; k < (Key *)(node->keys + node->endkeys); k = k->next()) {
  311.         /* Find right place in this level */
  312.         if (! (compare = (* ndx->cmpfn)(key, k->data, n))) {
  313.             if (k->lson) {    /* Lower level keys -- recurse */
  314.                 PUSH(node, k);
  315.                 rcd = _find(key, k->lson);
  316.                 if (rcd) return rcd;
  317.                 node = POP(k);
  318.             }
  319.                 /* We have the key */
  320.             PUSH(node, k);                  // Save it on the stack
  321.             ckey.keycpy(k);                 // and copy to current key
  322.             return ckey.offset;
  323.         }
  324.         if (compare < 0) break;
  325.     }
  326.  
  327.     /* Ran into larger key or at end of this level */
  328.     PUSH(node, k);      /* Update stack */
  329.     rcd = 0;
  330.     if (k->lson) /* More keys on right -- recurse */
  331.         rcd =  _find(key, k->lson);
  332.     if (! rcd) POP(k);
  333.     return rcd;
  334. }
  335.  
  336. DWORD Index::first(unsigned last)
  337. {
  338.     Node *node = getnode(root);
  339.     DWORD lson;
  340.     Key *kp;
  341.     
  342.     ndx = this;
  343.     if (! node->endkeys && ! ((Key *)(node->keys))->lson) return 0;
  344.     stacktop = 0;
  345.     /* Find lowermost leftmost key (or last) in the index, setting the stack */
  346.     while ((lson =
  347.         (kp = (Key *)(node->keys + (last? node->endkeys: 0)))->lson)!=0) {
  348.         PUSH(node, kp);
  349.         node = getnode(lson);
  350.     }
  351.     if (last) kp = kp->prev(node);
  352.     PUSH(node, kp);
  353.     ckey.keycpy(kp);
  354.     return ckey.offset;
  355. }
  356.  
  357. DWORD Index::next()
  358. {
  359.     Node *node;
  360.     Key *kp;
  361.     
  362.     ndx = this;
  363.         
  364.     /*  The state at return is that left by find():
  365.           The top of the stack is the node in which a key was last found
  366.           and the offset is that of the key.  */
  367.         
  368.     node = POP(kp);
  369.     kp = kp->next();
  370.  
  371.     while (kp->lson) {  /* Need to go down a level, at least */
  372.         PUSH(node, kp);
  373.         node = getnode(kp->lson);
  374.         kp = (Key *)node->keys;
  375.         continue;
  376.     }
  377.     while (kp == (Key *)(node->keys + node->endkeys)) {
  378.         if (stacktop == 0) return 0;
  379.         node = POP(kp);
  380.     }
  381.     PUSH(node, kp);
  382.     ckey.keycpy(kp);
  383.     return ckey.offset;
  384. }
  385.  
  386. DWORD Index::prev()
  387. {
  388.     Node *node;
  389.     Key *kp;
  390.  
  391.     ndx = this;
  392.     node = POP(kp);
  393.     while (kp->lson) {
  394.         PUSH(node, kp);
  395.         node = getnode(kp->lson);
  396.         kp = (Key *)(node->keys + node->endkeys);
  397.         }
  398.     kp = kp->prev(node);
  399.     while (! kp) {
  400.         if (stacktop) {
  401.             node = POP(kp);
  402.             kp = kp->prev(node);
  403.         }
  404.         else return 0;
  405.         }
  406.     PUSH(node, kp);
  407.     ckey.keycpy(kp);
  408.     return kp->offset;
  409. }
  410.  
  411. void Key::push(Node *node)
  412. {
  413.     Frame *stk = (Frame *)&ndx->stack[ndx->stacktop++];
  414.  
  415.     if (ndx->stacktop > stackdepth) fatal("Index stack overflow");
  416.     stk->node = node->offset;
  417.     stk->offset = (char *)this - (char *)node->keys;
  418. }
  419.  
  420. Node * Key::pop(Key *&k)
  421. {
  422.     Frame *stk = (Frame *)&ndx->stack[--ndx->stacktop];
  423.     Node *node = ndx->getnode(stk->node);
  424.     k = (Key *)(node->keys + stk->offset);
  425.     return node;
  426. }
  427.  
  428. int Node::split()
  429. {
  430.     Node *parent, *added;
  431.     Key *kp, *kpop, *old, *pivot;
  432.     unsigned n, np;
  433.  
  434.     /* Find entry to be moved up a level */
  435.     kp = (Key *)(keys + endkeys/2);
  436.     pivot = kp->prev(this);
  437.     np = pivot->length();
  438.     old = pivot->next();
  439.     n = (char *)old - keys;    /* The entry goes to new node, for */
  440.     if (ndx->stacktop) {               /*   the moment */
  441.         /* If parent full, split it, then we will be back hopefully */
  442.         parent = kpop->pop(kpop);
  443.         if (pivot->length() + parent->endkeys >= maxendkeys)
  444.             return parent->split();
  445.         }
  446.  
  447.     /* Copy first keys and pivot to new node */
  448.  
  449.     added = ndx->newnode();
  450.     memcpy(added->keys, keys, n);
  451.     added->endkeys = n - np;
  452.     ((Key *)(added->keys + n))->lson = 0;
  453.  
  454.     /* Then move the remaining keys of the original node down */
  455.  
  456.     endkeys -= n;
  457.     memmove(keys , old, endkeys + sizeof(DWORD));
  458.     cache[1].dirty = 1;
  459.  
  460.     /* If it was the root, create a new one */
  461.  
  462.     if (offset == ndx->root) {
  463.         parent = ndx->newnode();
  464.         kpop = (Key *)parent->keys ;
  465.         kpop->lson = offset;
  466.         ndx->root = parent->offset;
  467.         }
  468.  
  469.     /* Put the pivot in the next higher level */
  470.  
  471.     pivot = (Key *)((char *)added->keys + added->endkeys);
  472.     parent->shiftup(kpop, pivot->length());
  473.     kpop->keycpy(pivot);
  474.     kpop->lson = added->offset;   /* Pivot may have a lson! */
  475.     return cache[0].dirty = 1;
  476. }
  477.  
  478. void Node::shiftup(Key *kp, unsigned n)
  479. {
  480.     int m = keys + endkeys - (char *)kp + sizeof(DWORD);
  481.  
  482.     memmove((char *)kp + n, kp, m);
  483.     endkeys += n;
  484.     cache[0].dirty = 1;
  485. }
  486.  
  487. void Node::shiftdn(Key *kp, unsigned n, unsigned leave)
  488. {
  489.     int m = keys + endkeys - (char *)kp + sizeof(DWORD);
  490.     DWORD link;
  491.  
  492.     if (! leave) memmove(kp, (char *)kp + n, m);
  493.     endkeys -= n;
  494.     cache[0].dirty = 1;
  495.     if (endkeys || kp->lson || ! ndx->stacktop) return;
  496.     link = offset;
  497.     offset = ndx->freelist;
  498.     ndx->freelist = link;
  499.     ndx->write(link, this, nodesize);   /* Have to do this here! */
  500.     cache[0].dirty = 0;
  501.     kp->pop(kp);
  502.     kp->lson = 0;
  503.     ndx->stacktop++;
  504.     cache[0].dirty = 1;             /* POP changed cache[0] !!! */
  505. }
  506.  
  507.  
  508. Key * Key::prev(Node *node)
  509. {
  510.     Key *pk = (Key *)node->keys, *k = pk;
  511.  
  512.     if (pk == this) return NULL;
  513.     while (k < this) {
  514.         pk = k;
  515.         k = k->next();
  516.     }
  517.     return pk;
  518. }
  519.  
  520. void fatal(char *format, ...)
  521. {
  522.     va_list argptr;
  523.  
  524.     fprintf(stderr, "FATAL ERROR: ");
  525.     va_start(argptr, format);
  526.     vprintf(format, argptr);
  527.     va_end(argptr);
  528.     fputs("\n", stderr);
  529.     exit(-1);
  530. }
  531.  
  532.